发表更新题解40 分钟读完 (大约6030个字)

2022巅峰极客 Crypto

有瓜吃，美滋滋。

题目质量一般，知识问答还全是搬运今年 ciscn 的。
然后三个队友都没啥空，就我一个做了两道密码，排 88 名，对我这个菜鸡来说也还行吧。

point-power

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import *
from gmpy2 import *
from random import *
from secrets import flag

assert len(flag)==42
p=getPrime(600)
a=bytes_to_long(flag)
b=randrange(2,p-1)
E=EllipticCurve(GF(p),[a,b])
G=E.random_element()

x1,y1,_=G
G=2*G
x2,y2,_=G

print(f"p = {p}")
print(f"b = {b}")
print(f"x1 = {x1}")
print(f"x2 = {x2}")
'''
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
'''

这题完全是现学现卖，之前只听说过椭圆曲线，然后就跑去学抽代忘记回来了。。。
首先查到椭圆曲线的加法（两点相同的情形）：
$$
x_2=m^2-2x_1\pmod p \ with \ m=\frac{3x_1^2+a}{2y_1}
$$
又在 Sagemath 文档查到曲线定义 $y_1^2=x_1^3+ax_1+b$ ，就能联立出一个一元二次方程，exp 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727

K = GF(p)
n=(K(x2+2*x1)).sqrt()
P.<x>= PolynomialRing(K)
A=1
B=6*x1**2-4*n**2*x1
C=-(4*n**2*x1**3+4*n**2*b-9*x1**4)
f=A*x**2+B*x+C
roots=f.roots()
print(roots)
flag=roots[1][0]
from Crypto.Util.number import *
print(long_to_bytes(int(flag)))

strange curve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
from Crypto.Util.number import *
from gmpy2 import *
from secrets import flag
import random

def add(P,Q):
    (x1,y1)=P
    (x2,y2)=Q


    x3=(x1+x2)*(1+y1*y2)*invert((1+x1*x2)*(1-y1*y2),p)%p
    y3=(y1+y2)*(1+x1*x2)*invert((1-x1*x2)*(1+y1*y2),p)%p

    return (x3,y3)

def mul(e,P):
    Q=(0,0)
    e=e%p
    while e:
        if e&1:
            Q=add(Q,P)
        P=add(P,P)
        e>>=1
    return Q

def Legendre(a,p):
    return (pow((a%p+p)%p,(p-1)//2,p))%p

def get_ts(p):
    p=p-1
    count=0
    while p%2==0:
        count+=1
        p=p//2
    return count,p

def get_nonre(p):
    a=random.randint(1,p)
    while Legendre(a,p)==1:
        a=random.randint(1,p)
    return a

def amm2(a,p):
    t,s=get_ts(p)
    ta=pow(get_nonre(p),s,p)
    tb=pow(a,s,p)
    h=1
    for i in range(1,t):
        d=pow(tb,2**t-1-i,p)
        if d==1:
            k=0
        else:
            k=1
        tb=(tb*pow(ta,2*k,p))%p
        h=(h*pow(ta,k,p))%p
        ta=pow(ta,2,p)
    return h*pow(a,(s+1)//2,p)%p  

def solve(a,b,c,p):
    tmpa=1
    tmpb=b*inverse(a,p)%p
    tmpc=c*inverse(a,p)%p
    assert Legendre(tmpb**2*inverse(4,p)-tmpc,p)==1
    res1=(amm2(tmpb**2*inverse(4,p)-tmpc,p)-tmpb*inverse(2,p))%p
    res2=(-amm2(tmpb**2*inverse(4,p)-tmpc,p)-tmpb*inverse(2,p))%p
    return (res1,res2)

def lift(x,a,b,p):
    tmp=b*(x**2-1)*inverse(a*x,p)%p
    return solve(1,-tmp,-1,p)[0]

p=9410547699903726871336507117271550134683191140146415131394654141737636910570480327296351841515571767317596027931492843621727002889086193529096531342265353
a=54733430689690725746438325219044741824500093621550218736194675295708808435509
b=75237024593957256761258687646797952793573177095902495908321724558796076392871
x=bytes_to_long(flag)

while True:
    try:
        y=lift(x,a,b,p)
        break
    except:
        x+=1
        continue

assert a*x*(y**2-1)%p==b*y*(x**2-1)%p

P=(x,y)
e=65537

eP=mul(e,P)
print(f"P = {P}")
print(f"eP = {eP}")
'''
P = (56006392793427940134514899557008545913996191831278248640996846111183757392968770895731003245209281149, 5533217632352976155681815016236825302418119286774481415122941272968513081846849158651480192550482691343283818244963282636939305751909505213138032238524899)
eP = (mpz(8694229840573103722999959579565187489450818138005222030156495740841851804943200684116883831426548909867463656993852596745698999492932194245562062558787005), mpz(9279986963919197374405152604360936066932975197577643570458423456304679111057526702737279809805694360981565554506626018364382736924914907001214909905449002))
'''

这题真的是蚌不住，刚放出来解出数就蹭蹭往上涨，还有点怀疑人生，然后仔细观察题目，一看上面，什么玩意，再看下面，什么玩意。。。
直接拿第一个数 long_to_bytes ，得到 flag。

Learning with fault

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from Crypto.Util.number import *
from gmpy2 import *
from secrets import flag
import os

class RSA():
    def __init__(self,p,q,e):
        self.p=p
        self.q=q
        self.e=e
        self.phi=(p-1)*(q-1)
        self.d=invert(self.e,self.phi)
        self.dp=self.d%(p-1)
        self.dq=self.d%(q-1)
        self.n=p*q
        self.N=getPrime(512)*getPrime(512)

    def sign(self,message):
        m=bytes_to_long(message)
        sig_p=pow(m,self.dp,self.p)
        sig_q=pow(m,self.dq,self.q)
        alpha=q*invert(q,p)
        beta=p*invert(p,q)
        return long_to_bytes((alpha*sig_p+beta*sig_q)%self.n)

    def corrupt_sign(self,message):
        m=bytes_to_long(message)
        sig_p=pow(m,self.dp,self.p)
        sig_q=pow(m,self.dq,self.q)
        alpha=q*invert(q,p)
        beta=p*invert(p,q)
        return long_to_bytes((alpha*sig_p+beta*sig_q)%self.N)

    def verify(self,message,sign):
        return long_to_bytes(pow(bytes_to_long(sign),self.e,self.n))==message

p=getPrime(512)
q=getPrime(512)
e=65537
rsa=RSA(p,q,e)

with open("sign.txt","w") as f1:
    with open("corrupted_sign.txt","w") as f2:
        for _ in range(6):
            message=os.urandom(64)
            sign=rsa.sign(message)
            corrupted_sign=rsa.corrupt_sign(message)
            assert rsa.verify(message,sign)
            f1.write(str(sign)+'\n')
            f2.write(str(corrupted_sign)+'\n')

enc=pow(bytes_to_long(flag),rsa.e,rsa.n)
print(f"n = {rsa.n}")
print(f"N = {rsa.N}")
print(f"e = {rsa.e}")
print(f"enc = {enc}")
'''
n = 99670316685463632788041383175090257045961799409733877510733415402955763322569510896091638507050126669571444467488936880059210773298729542608112756526719533574432327269721804307073353651955251188547245641771980139488000798458617636759823027148955008149512692983471670488580994385743789385091027299901520585729
N = 81332992898551792936282861980393365170738006789835182134055801566584228471896473385776004610279937176800796971820133195300006470892468060034368863410462219133248069442508287516929262751427926825122839525496671527936622212986733708071962237633082743396115729744192159064241674410003857168101669882043743570731
e = 65537
enc = 2476965183785968993595493003363618829317072815989584886372189393899395623714779397354978469504773556228655475355703015337932838278988328384587983506790841663233499939173166353582189202860394411808445422387063648198432242875738065748287034529713834303346017134249834382745931627301273142828893469374138264396
'''

出题论文：https://eprint.iacr.org/2011/388.pdf
这题一开始是搜到了论文，瞟了两眼，以为不是，就没看下去了。。。
后来学长发给我这篇，我焯了两个钟复现出来了，说不定真有机会现场解出，唉还是太菜。
照着论文的 Attack Summary 敲就行了，一开始没理解到 $z$ 向量的意思，直接从格子拿，跑不出来，学长问我 $a$ 和 $b$ 的选取是不是有问题，我才知道要枚举出所有 $x$ 和 $y$ 。然后 $a$ 和 $b$ 在 0 到 10 间选取也不行，改成了 -10 到 10 。
exp 如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from tqdm import tqdm
from itertools import combinations
from sage.all import *
from Crypto.Util.number import *
co_sig = [b"\x17\x8bb3\x11\x1b\xb9\xb9\xc6M\xb0\xaa\x07-\x1ar\xff\xfb\xb4&H7!\xb8\xa1\xce\x07\x8b\x84M\x0bw=m\x193Oc\x97w\x8f\xffy4\xa1\x99\xfcW\xf9|\xeb\xa4\x00\x1eD*\xe8-'\xa9\xef\x9d\x13*\xf4\xbe\x9d\x9b&w\xcb\xfd\xb3\xb6\xa3n\xb8\xb4\x97vT\xec@\x86\xd1R\xb0\n\xe1uC\xbc\x14\xeb\xceSu&'{\xb9\x12\x90\x82\xc7,\xdbr\xebP\xe1j\x11E\xd5\x17\xe1\xd0D\xe7z\x94vt\xbf\x1a\xc4+",
          b'\x1dJ\xc5\xb2\xbe\x05\xe6\xc8T\n\xbe"\xbeU\xed\xba\xec\x85\x05\x8b\x8ayE\xa3}0\x1dk\xa7\x10\xe2E\x19\xfe\x10\x90\xef\r\xdbV\x8b\x87|(\xd1\xb5\xfd\xb9\x14\x84\x05\x03\x81\xc8\xf6\xe5\x8a\x92\xa0\x01I\x8aG:\xc19\x9e\xf0\x8eZ\\Yx\x80|\xb7\x80\x0e\xcd\xa3\xba6\xf8\x98\xb1pB\x05\x8aT#\xbf\x1e\x1b~\xcb\xf5\t\xa2H9\xc9n\x81e\xa2\x15\x97\x11\xe4\x93\xf2\xe6\x80\x97\x99G\xb5\xfe\x07/\xd2\xbd\xad\xcf\x04\x9e\xd0',
          b'Gs\xda\xb8\x8a\x85\xccK\xf7\xa8y\x16\xa5\xf0\x06\xbe\xeb\x83&}a\x85q\x8d:\x1fSb\xb8\xc5\x84\xba*[\xe7\xbb{\x86\xd3\xb3r\xb6\xaaCN\x93\x1d<(\xe2\x1c;\x8crU\x8fD=W\xa7\x0b\xc7\xeag\x96\x06\xd6\xbb\xe4\x04b\xd8\x02\x12\xd6\xfa2\x1e#\xf0\xde\x8b\x88M\xd2\xf47\\\x98\xe0\x04Fu\x1bsy\xf2\xc4\xad\xd6Y\x81u~B:\xd2\x1f\xb3\xab\x01:\xfa\xdf\x19J8\xd0\x18RN\xfe,CA\x15\xb3\xe0',
          b"0I\xda5\x9f\x05v\x17\xdc\xd4q\xd6\x83,\x9d\r\xccc\x8a\xa1\xd4U\xd3\x18\xc9\xc6g\xcd\nX\x99Ah\xed}\xf3\xb1(\xd5I\xc6\x0f@yw9\x9d\xfdv\x15x\xeaRA\xd6\xb0\x1e\xb5B\xe5\x05cc\x06m\xf4NN'\x02q\x1a\x11\xe4\x87P:\xc8\x11a\x9f\xbd\x9c\x98x\xda\xea\xc4\xa8f\x89s\xcaJ\x7f\xeb\xd8\xc1G#\xf4\xdc\xe2\x01\xf2\xa5\x95\x19`)2!\xf5\xb9\xf0\xf2\xbb\xf8\x0bF&&`\xfd*\xe1\xf2\x9c",
          b':\x99/Hxt\xd1\xd4\xaaB\xd6H\x16\xe1\xc9\xe2\xb3\xc3\xa9b\xd3\x96\x9c\x05x6\xf1\xc3d\xa2\xd1U+.\x1b\xac^\xf6Mh7\xb7\x03\x8e\xdc\xca\x0bn\xac\xed\x92\xb8x\x04)\x0f|\x11\xcc\xfa\xf2\\\xba\xee\xc4X\xa8(\x05\xf2\xb5\x8f&\xf3\xff\x1eB\xe7\x94\xf4\xa6\x00!\xe5v\xd9x\xf0s\x94\xf4D(\xa9g\x118\xa7z\x83\xad\xdb\xe6\xe3\xe7\xf8\xf2\xef\xe5@\xe9\x13\x00OB\xcc\x05\xd1,_=\xd2/Og\x81\xa6+',
          b'\x1c|\xb6\xcc\xdfj\xc5\xa0s\xac w\xa6\xf2\x87D\xe3\xf9Y\xf5=\xf0\x0b\xd9\xea\x89,+e\x1e\xb7m#\x99\xd1\x87\x17Z\xed\x1d\xc8\x97;\xa0K\x05.\xaa<\xc6s\xcf\xa2\xa2\\PO\x12&\xb4\x11\xec\xad\x10\xf8\xf7\xd1\xd3_\x80\x17\xe0\x1eP\x93\xe3\xc2\x1e\x03\xea]^\xc6a\x9c\xcb\x90\xbb\x9f\x8by\xa5dhM\xce\xc7\xbc\xf7\xafe\xcf\xc1\xf1\x18@\x1e\xe2\xdb\xfb\xe4^\xc8\xe7\x19\xccnY\xc6o\x7fL\x9fV\xd4\xc4\x15\xe8',
          ]
sig = [b'\t\x8b\xde\x98\x84\x1d\x9e\xd4\xa0\xb7f\xe0\x05\xb1\xbd8\xb9G\xe3\x0c\x83\x8a\xe5\xf0G7\x12\x1eT\x85o-B\xe4_\xd2\x04\xd9:\xab\xdf\xa1 \x8f\xedt+\x0f\xce\xb5\x90\xaaK\xf0U~v=\x84\xe7$G\xf5\xfb\xd3ok~V\x1a\xec&\x15\x18Y\x0c\x80u\xafF\xf1\x10\x9f\xf2\xe6\xa6\x9a\xbb\xbd+\xa4l\xa9\x11\xd5\t\x13\x16\xa3\xde\xe1\xdfZ\xa9$r\xb5`\xc9"\x11\xab\xc5\x87\xc4\x1d@\x9e\xa4t\xdb#\xbdj\xcb\x95\xefK',
       b'z/\xd6\xfb\xd8\xfa\xc4\xed\xbd\x99\xd0\xa0\x90\xcb\xca\x83\xd8B\xa7\xf4\xbd\xe0\xc2&\x1aQl(\xd6p\x8f\x89=tT\xf1(\xeb\xab\x84[oR\x1fl=\xda\xf5\x18q\x8f\xa7k\x00\x1b\x1a\x0ei\x1fa.ho\x15\x04\x12\xe4\xc2\xd7\x19\x92\xc3\x9b\xfe\xd5\xb6R\xf8\x95\x9fr\x93\xddD\x1c[\x873\xd5\x06\x1b\xa5\x82/6\x9a\x13\xcf\xa4\xcd\x0e]\t\xad?\xd6\x84\r\x90\xef\x86\xf15)\xe34\xf7\xb77\xef\x0c&\xdb8\xa6\xe0\xa5a',
       b'U\x0b\xf6\x9cm])1\xe2\xad\xf9G\x8f\xa2\xbc}\xd7\x18\x89\xa4\xfdFQ\x80m"\xf9\to^\xd9A\x98\xd2\xca\x1e(b\xa8\xbe\xc2m\xf7\n[O\x00\xbc\x87\x17\xed\x0cG\xf2=H\x0e\xc0\x14+\xcb\xd0\x1feT2\xf2Th\xec\xc2\xcf>6,<\x88X\x8f\xe9g\xa8\x00\xafr\x05\x95\rj\x9c\xc6\n\xbb\x8a\x019\xc1\x1ef#\x02[Rh\xd8\xdc|{6\xeb\xe8U\x91\xa4\xeb}\xf4s;E\xe72$i\xdft\xff\'',
       b'[\x94\x95T\xf4\xc4\xca\x8drO\x80\x14\xc9<H\xa2a\xdc\xf4`\xac>\xab\x03\xfa\x80Sx\x99\x14\x83$U\x0b\xfa\x8fv\xfd\xda\x1a\xa0\xebY\xaa\x01\xe2XsG\t\xcf\xae\xa0\xbf\x82iG\tQ \xb1\xfe\xa5k\x12\xd9\x12\xf7\x95\xa3\xa5\x8d`z\x19\x1a\x90-\x9aj\x15\xf6f>\x18\x08\xb8\x1f\x88\x1a\x80Th\xd0\x15\x9bw#\'`K\xa5\xf1\xbf"\xe79\xaf\xc7z%p\xa5\x9f\x14\xef\'1\x11\x05Gg\xe9\xda\xc9\x18~[',
       b':\xefRE\xd7\xa1?\xf3\xb5\xf7\xdd\xe2\xb6~\x85014\xc0\x8a\x80\xe1\xb5#\x94\x10\xb2\xa0\xfe\x87\xd1t\xc3$&\xde8\x195\xcd\xf4@3\x15\xcaK\xcc\xcd\r:\x83*\xd7l\xb6\xf2} \tJ\xb5xKfjh.\xfb\xb5\x91\xc6\xf2x\x8e\x83\xdc\xc3\xef\x8b\x8dW\xa6\xa6\xb0w\xd8\xf2G\xa5-\xc3\x87\x17;\xedH`:\xcd\x08ts\x9eqPE\xd7\xfc\xc4\x98\xb5\xe0\xad\xb7A\x7f\xcb\x01\xbd\x98\xd3Ea\xb9\x07\x80\xf8\x19',
       b"8\xca\x7f!;\\\xde\x1b\x80i\x9b!\x1c??u\x13\x955\xd0xG\xff\xd7\xba\xfe+\x95\x0eu^\x15\x1a\x0e*\xfe\x8a\xafM\xc0\xd1Ty\xd7\xf1\xa7@\xd6\xa6\xee\x0c:It\x1a\xeag\xfc\x0c\xaf\x02<\x03T)\xeb\xb0\x15\x1cz\x85\x992\xa9\xbe\x9bm\xc4D\x83\xf7\xb5T\xdd9?\x94\xd4\x13\xb4\xb3\x8d\xa9\x92\x9dt\x86\xdb\x0b$\x19l\xb1\xb9\x05'o\xf3!\t\x01\x93'z\x15P\x88\xd7iN\n\x8bA\xb5\xd2}\xe8\x10"
       ]
n = 99670316685463632788041383175090257045961799409733877510733415402955763322569510896091638507050126669571444467488936880059210773298729542608112756526719533574432327269721804307073353651955251188547245641771980139488000798458617636759823027148955008149512692983471670488580994385743789385091027299901520585729
N = 81332992898551792936282861980393365170738006789835182134055801566584228471896473385776004610279937176800796971820133195300006470892468060034368863410462219133248069442508287516929262751427926825122839525496671527936622212986733708071962237633082743396115729744192159064241674410003857168101669882043743570731
e = 65537
enc = 2476965183785968993595493003363618829317072815989584886372189393899395623714779397354978469504773556228655475355703015337932838278988328384587983506790841663233499939173166353582189202860394411808445422387063648198432242875738065748287034529713834303346017134249834382745931627301273142828893469374138264396


def orthogonal_lattice(B):
    _d, _n = B.nrows(), B.ncols()
    _c = 2 ** min(((_n-1)/2+(_n-_d)*(_n-_d-1)/4), 20)
    for b in B:
        _c *= b.norm()
    B_bot = (ceil(_c)*B).stack(identity_matrix(ZZ, _n))
    B_r = B_bot.transpose().LLL()
    LB = B_r.matrix_from_rows_and_columns(range(_n-_d), range(_d, _n+_d))
    assert (B*LB.transpose()).is_zero()
    return LB


v = [crt([bytes_to_long(co_sig[i]), bytes_to_long(sig[i])], [N, n])
     for i in range(6)]

Lv = orthogonal_lattice(matrix(ZZ, v))

result = orthogonal_lattice(Lv.matrix_from_rows(range(0, 6-2)))

for x, y in combinations(result, 2):
    for a in tqdm(range(-10, 10)):
        for b in range(-10, 10):
            z = a*x+b*y
            if z.norm() > sqrt(6*n):
                continue
            else:
                vv = vector(v)-z
                for i in vv:
                    if gcd(i, n) != 1:
                        p = gcd(i, n)
                        assert n % gcd(i, n) == 0
                        q = n//p
                        phi = (p-1)*(q-1)
                        d = inverse_mod(e, phi)
                        m = long_to_bytes(int(pow(enc, d, n)))
                        print(m)
                        exit()

原理

RSA-CRT 签名中计算了：
$$
\sigma_p=\mu(m)^d\mod \ p \\ \sigma_q=\mu(m)^d\mod \ q
$$
然后签名 $\sigma=\sigma_p\cdot\alpha+\sigma_q\cdot\beta$ ，其中 $\alpha=q\cdot(q^{-1}\mod\ p)$ ， $\beta=p\cdot(p^{-1}\mod\ q)$ 。
题目中给出 6 对签名，每对签名用 CRT 不难算出
$$
v=\sigma_p\cdot\alpha+\sigma_q\cdot\beta \mod N\cdot N’
$$
其中 $\sigma_p$ 和 $\sigma_q$ 和 $N/2$ 一个数量级， $\alpha$ 和 $\beta$ 又和 $N$ 一个数量级，故右式远小于 $N\cdot N’$ ，那么上式在整数域上是成立的。
一对算不出，但是多对可以，组成向量，有：
$$
\boldsymbol{v}=\alpha\boldsymbol{x}+\beta\boldsymbol{y}
$$
其中 $\boldsymbol{x}$ 和 $\boldsymbol{y}$ 是分量 $n/2$ 位的未知向量， $\alpha$ 和 $\beta$ 是有关 $p$ 和 $q$ 的 CRT 系数。
不难计算出一组与 $\mathbb{Z}^\ell$ 中正交于 $\boldsymbol{v}$ 的向量的格 $\boldsymbol{v}^\bot \in \mathbb{Z}^\ell$ 的约化基 ${\boldsymbol{b}_1,…,\boldsymbol{b}_{\ell-1}}$ 。（可能此时你会疑惑为什么是 ${\ell-1}$ 个向量，下面的拓展里有解释）
特别地，我们有：
$$
\alpha \langle \boldsymbol{b}_j,\boldsymbol{x} \rangle + \beta \langle \boldsymbol{b}_j,\boldsymbol{y} \rangle = 0 \quad \mathrm{for} \ j=1,2,\ldots,\ell-1
$$
（也不是很特别的感觉）
现在观察方程 $\alpha\cdot u+\beta\cdot v=0$ ，最小的非零解 $(u,v)\in \mathbb{Z}^2$ 是 $\pm(\beta,-\alpha)/g$ ，其中 $g=\gcd(\alpha,\beta)$ 盲猜是非常小的（经测试基本在10以内），意味着 $|u|,|v|\geq\mathit{\Omega}(N)$ 中 $\mathit{\Omega}$ 常量是非常小的。（啥玩意？）对 $j=1,2,\ldots,\ell-1$ ，有以下两种可能：

情形1：$\langle \boldsymbol{b}_j,\boldsymbol{x} \rangle = \langle \boldsymbol{b}_j,\boldsymbol{y} \rangle = 0$ 。此时 $\boldsymbol{b}_j$ 属于 $\mathbb{Z}^\ell$ 中与 $\boldsymbol{x}$ 和 $\boldsymbol{y}$ 正交的向量的格 $L={\boldsymbol{x},\boldsymbol{y}}^\bot$

情形2：$\langle \boldsymbol{b}_j,\boldsymbol{x} \rangle$ 和 $\langle \boldsymbol{b}_j,\boldsymbol{y} \rangle$ 有绝对值 $\geq \mathit{\Omega}(N)$ ，其中 $\mathit{\Omega}(N)$ 是一个小常数。因为 $\boldsymbol{x}$ 和 $\boldsymbol{y}$ 的范数都不超过 $\sqrt{\ell N}$ ，由柯西-施瓦茨不等式，这意味着 $||\boldsymbol{b}_j||\geq \mathit{\Omega}(\sqrt{\ell N})$

因为格 $L={\boldsymbol{x},\boldsymbol{y}}^\bot$ 的秩是 $\ell-2$ ，当全部 $\ell-1$ 个向量 $\boldsymbol{b}_j$ 线性无关时情形1不成立，所以最长的 $\boldsymbol{b}_{\ell-1}$ 应该在情形2中，因此 $||\boldsymbol{b}_{\ell-1}||\geq \mathit{\Omega}(\sqrt{\ell N})$ 。另一方面，其他向量形成一个秩为 $\ell-2$ 的格，且体积
$$
V=\mathrm{vol}(\mathbb{Z}\boldsymbol{b}_1\oplus\cdots\oplus\mathbb{Z}\boldsymbol{b}_{\ell-2})\approx\frac{\mathrm{vol}(\boldsymbol{v}^\bot)}{||\boldsymbol{b}_{\ell-1}||}=\frac{||\boldsymbol{v}||}{||\boldsymbol{b}_{\ell-1}||}\leq \frac{\sqrt{\ell}\cdot N^{3/2}}{\mathit{\Omega}(\sqrt{N/\ell})}=O(\ell N)
$$
盲猜是一个随机的格。特别地，我们有：
$$
||\boldsymbol{b}_j||=O(\sqrt{\ell-2}\cdot V^{1/(\ell-2)})=O(\ell^{1/2+1/(\ell-2)}\cdot N^{1/(\ell-2)})\quad\mathrm{for} \ j=1,2,\ldots,\ell-2
$$

一旦 $\ell \geq 5$ ，这个长度就远小于 $\sqrt{N/\ell}$ 。假设是这种情况，那么对于 $j=1,2,…,\ell-2$ ， $\boldsymbol{b}_j$ 应该是情形1中。这意味着这些向量生成 $L={\boldsymbol{x},\boldsymbol{y}}^\bot$ 中一个满秩的子格 $L’=\mathbb{Z}\boldsymbol{b}_1\oplus\cdots\oplus\mathbb{Z}\boldsymbol{b}_{\ell-2}$ 。
取正交格，我们得到 $(L’)^\bot \supset L^\bot=\mathbb{Z}\boldsymbol{x}\oplus\mathbb{Z}\boldsymbol{y} $。因此， $\boldsymbol{x}$ 和 $\boldsymbol{y}$ 属于 $L’$ 的正交格 $(L’)^\bot$ 。令 ${\boldsymbol{x’},\boldsymbol{y’}}$ 为一组该格的约化基，我们可以枚举 $(L’)^\bot$ 中的长度不超过 $\sqrt{\ell N}$ 且为 $\boldsymbol{x’}$ 和 $\boldsymbol{y’}$ 线性组合的所有格向量。高斯启发式表明这大约为：
$$
\frac{\pi(\sqrt{\ell N})^2}{\mathrm{vol}((L’)^\bot)}=\frac{\pi\ell N}{V}=O(1)
$$
这样的向量，所以这肯定是可行的。对这些向量 $\boldsymbol{z}$ ，我们计算 $\gcd(\boldsymbol{v}-\boldsymbol{z},N)$ 。我们将因此很快在其中找到 $\gcd(\boldsymbol{v}-\boldsymbol{x},N)$ ，因为 $\boldsymbol{x}$ 是一个 $(L’)^\bot$ 中长度 $\leq\sqrt{\ell N}$ 的向量。但根据 $\boldsymbol{v}$ 的定义，我们有：
$$
\boldsymbol{v}=\boldsymbol{x}\mod p\\
\boldsymbol{v}=\boldsymbol{y}\mod q
$$
故 $\gcd(\boldsymbol{v}-\boldsymbol{x},N)=p$ ，从而分解 $N$ 。

拓展阅读-正交格

令 $\mathbf{b}_1,…,\mathbf{b}_d$ 为 $\mathit{\Lambda}$ （这玩意念Lambda）中的向量。如果这 $d$ 个向量在 $\mathbf{Z}$ 上线性无关且 $\mathit{\Lambda}$ 中的任意元素可以由 $\mathbf{b}_i$ 整系数线性表出，则这 $d$ 个向量形成 $\mathit{\Lambda}$ 中的一组基。 $\mathit{\Lambda}$ 中至少存在一组基。 $\mathit{\Lambda}$ 的基都有相同的基数，称为 $\mathit{\Lambda}$ 的维度。

如果 $\mathit{\Omega}$ 包含 $\mathit{\Lambda}$ ，且两者有相同的维度，则称 $\mathit{\Lambda}$ 为 $\mathit{\Omega}$ 在 $\mathbf{Z}^n$ 上的一个子格。（子格的定义？） $\mathit{\Lambda}$ 的所有基张成相同的 $\mathbf{Q}^n$ 的 $Q$ 向量子空间（啥玩意？），记为 $E_{\mathit{\Lambda}}$ 。 $\mathbf{Q}^n$ 上 $E_{\mathit{\Lambda}}$ 的维度与 $\mathit{\Lambda}$ 的维度相同。令格 $\overline{\mathit{\Lambda}}=E_{\mathit{\Lambda}}\cap\mathbf{Z}^n$ 。 $\mathit{\Lambda}$ 是 $\overline{\mathit{\Lambda}}$ 的一个子格。如果 $\mathit{\Lambda}=\overline{\mathit{\Lambda}}$ ，那么我们称 $\mathit{\Lambda}$ 是一个完备格，特别的， $\overline{\mathit{\Lambda}}$ 是一个完备格。

笔者注记：
这里首先将 $\mathit{\Lambda}$ 张成一个有理数空间，不局限于整系数向量组合了，记为 $E_{\mathit{\Lambda}}$ 的E我猜是欧几里得的意思？然后与 $\mathbf{Z}^n$ 相交得到的是整数点集合 $\overline{\mathit{\Lambda}}$ ，如此 $\mathit{\Lambda}$ 是 $\overline{\mathit{\Lambda}}$ 子格的事应该挺自然的。然后如果两者相等，想象一下，都那样张成了都找不到新的点，那这个格确实也挺完备。
PS:发现自己念了十年的欧几里得，难怪输入法打不出来（）

令 $(\mathbf{x},\mathbf{y})\rightarrow\mathbf{x}.\mathbf{y}$ 为一般意义上的欧里几德内积， $||.||$ 是它对应的范数 （奇怪的表示方法）。令 $F=(E_{\mathit{\Lambda}})^-$ 是关于该内积的正交向量子空间。我们定义正交格 $\mathit{\Lambda}^-=F\cap\mathbf{Z}^n$ 。因此， $\mathit{\Lambda}^-$ 是一个 $\mathbf{Z}^n$ 上的完备格，其维度为 $n-d$ 。这意味着 $(\mathit{\Lambda}^-)^-$ 等于 $\overline{\mathit{\Lambda}}$ 。令 $\mathcal{B}=(\mathbf{b}_1,…,\mathbf{b}_d)$ 为 $\mathit{\Lambda}$ 的一组基。

笔者注记：
看到这就有点迷糊了，捋一捋： $E_{\mathit{\Lambda}}$ 是 $\mathit{\Lambda}$ 张成出的有理空间，然后 $F$ 是其正交向量子空间，即任意从 $\mathit{\Lambda}$ 和 $F$ 分别抓两个向量出来，其内积都为 $0$ 。
再然后 $\mathit{\Lambda}^-$ 是 $F$ 的一个子格，注意到 $\mathit{\Lambda}^-$ 把 $F$ 所有整数点都框进去了，这就很有意思了，由上面的定义就不难得出正交格 $\mathit{\Lambda}^-$ 是一个 $\mathbf{Z}^n$ 上的完备格。
至于其维度为何是 $n-d$ ，有个概念叫正交补，就是正交空间的维数是刚刚好的，对于列空间维数为 $r$ 的矩阵 $A_{r\times m}$ ，其左零空间的维数是 $m-r$ ，相加恰好为 $m$ 。举例来说，三维中与线正交的是二维空间，与面正交的是一维空间。
这篇 paper 习惯用 $E^-$ 表示正交向量子空间，但似乎 $E^\bot$ 的写法较为广泛。

在 $\mathbf{Z}^n$ 的正则基上解析每个 $\mathbf{b}_j$ 如下：

$$
\mathbf{b}_j =
\begin{pmatrix}
b_{1,j} \\
b_{2,j} \\
\vdots \\
b_{n,j}
\end{pmatrix}
$$
（这里吐槽一下，由于下划线和 Markdown 语法有冲突，如果不加反斜杠， $b_j$ 写成 $\mathbf{b}_j$ Latex 就会炸，下文一开始也炸了几回，弄了几次才发现是这问题）

定义整数 $n\times d$ 的整数矩阵 $B=(b_{i,j})_{1\leq i\leq n,1\leq j\leq d}$ ，格 $\mathit{\Lambda}$ 由 $B$ 的列向量张成，我们称 $\mathit{\Lambda}$ 由 $B$ 张成。令 $Q={^tB}B$ 为 $d\times d$ 的对称 Gram 矩阵。 $Q$ 的行列式是与 $\mathcal{B}$ 无关的正整数。 $\mathit{\Lambda}$ 的行列式被定义为 $\det(\mathit{\Lambda})=\sqrt{\det(B)}$ 。

笔者注记：
这是的 ${^tB}$ 应该是 $B^T$ 的意思，又是奇怪的写法（）
至于 Gram 矩阵，中文音译为格拉姆矩阵，对 $n$ 维欧氏空间上的 $k$ 个向量，其 Gram 矩阵为
$$
\triangle(\mathbf{v}_1,\dots,\mathbf{v}_k) =
\begin{pmatrix}
\langle\mathbf{v}_1,\mathbf{v}_1\rangle & \cdots & \langle\mathbf{v}_1,\mathbf{v}_k\rangle \\
\vdots & \ddots & \vdots \\
\langle\mathbf{v}_k,\mathbf{v}_1\rangle & \cdots & \langle\mathbf{v}_k,\mathbf{v}_k\rangle
\end{pmatrix}
$$
不难看出这个可以等价表示为 $V^T\times V$ ，得出的矩阵也显然是对称的。
这里 $\mathit{\Lambda}$ 不是一个方阵，故不能直接求出其行列式，那么就应该通过其 Gram 矩阵来求行列式，这里我觉得应该是 $\det(\mathit{\Lambda})=\sqrt{\det(Q)}$ ，但我不确定。

定理1 令 $\mathit{\Lambda}$ 为 $\mathbf{Z}^n$ 上的完备格，那么 $\det(\mathit{\Lambda}^-)=\det(\mathit{\Lambda})$ 。
证明：我们有 $\mathit{\Lambda}=E_{\mathit{\Lambda}}\cap\mathbf{Z}^n$ 和 $\mathit{\Lambda}^-=E_{\mathit{\Lambda}}^-\cap\mathbf{Z}^n$ 。从另一篇论文（我也没读过）我们知道：
$$
\det(\mathbf{Z}^n)=\frac{\det(E_{\mathit{\Lambda}}\cap\mathbf{Z}^n)}{\det((E_{\mathit{\Lambda}}^-)\cap(\mathbf{Z}^n)^*)}
$$
其中 $(\mathbf{Z}^n)^*$ 表示 $\mathbf{Z}^n$ 上的极格。但 $\det(\mathbf{Z}^n)=1$ （？为什么要说但呢？）且 $(\mathbf{Z}^n)^*=\mathbf{Z}^n$ ，故 $\det(\mathit{\Lambda}^-)=\det(\mathit{\Lambda})$ 。

推论2 令 $\mathit{\Lambda}$ 为 $\mathbf{Z}^n$ 上的格，那么 $\det((\mathit{\Lambda}^-)^-)=\det(\mathit{\Lambda}^-)=\det(\overline{\mathit{\Lambda}})$ 。

定理3 令 $(\mathbf{b}_1,…,\mathbf{b}_d)$为格$\mathit{\Lambda}$ 在 $\mathbf{Z}^n$ 上的一组 LLL 约化基，那么：

  1. $\det(\mathit{\Lambda})\leq \prod^d_{i=1}||\mathbf{b}_i||\leq 2^{d(d-1)/4}\det(\mathit{\Lambda})$
  2. 对任意线性无关的向量 $\mathbf{x}_1,…,\mathbf{x}_t\in\mathit{\Lambda}$ ，当 $1\leq j \leq t$ 时，有：

$$
||\mathbf{b}_j||\leq 2^{(d-1)/2}\max(||\mathbf{x}_1||,…,||\mathbf{x}_t||)
$$

我们现在描述计算正交格的一组 LLL 约化基的基本方法。令 $\mathcal{B}=(\mathbf{b}_1,…,\mathbf{b}_d)$ 为 $\mathit{\Lambda}$ 的一组基， $B=(b_{i,j})$ 为其对应的 $n\times d$ 的矩阵。令 $c$ 为一个正整数常量。定义 $\mathit{\Omega}$为$\mathbf{Z}^{n+d}$ 上由以下 $(n+d)\times n$ 矩阵张成的格。

$$
B^-=
\begin{pmatrix}
c\times b_{1,1} & c\times b_{2,1} & \cdots & c\times b_{n,1} \\
c\times b_{1,2} & c\times b_{2,2} & \cdots & c\times b_{n,2} \\
\vdots & \vdots & \ddots & \vdots \\
c\times b_{1,d} & c\times b_{2,d} & \cdots & c\times b_{n,d} \\
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1
\end{pmatrix}
$$
矩阵 $B^-$ 被分成两块：上面 $d\times n$ 部分是 $c\ {^tB}$ ，下面 $n\times n$ 部分是单位阵。
设 $p_{\uparrow}$ 和 $p_{\downarrow}$ 是两个投影，将 $\mathbf{Z}^{n+d}$ 的任何向量分别映射到由其前 $d$ 个坐标构成的 $\mathbf{Z}^d$ 向量和由其最后 $n$ 个坐标构成的 $\mathbf{Z}^n$ 向量，所有投影都与正则基有关。（这段翻译累死我了）
令 $\mathbf{x}$ 为 $\mathit{\Omega}$ 的一个向量并记 $\mathbf{y}=p_{\downarrow}(\mathbf{x})$ ，那么

$$
p_{\uparrow}(\mathbf{y})=
\begin{pmatrix}
\mathbf{y}.\mathbf{b}_1 \\
\vdots \\
\mathbf{y}.\mathbf{b}_d
\end{pmatrix}
$$
因此，当且仅当 $p_{\uparrow}(\mathbf{x})=0$ 时有 $\mathbf{y}\in \mathit{\Lambda}^-$ 。此外，如果 $||\mathbf{x}||\leq c$ ，那么 $p_{\uparrow}(\mathbf{x})=0$ 。

定理4 令 $(\mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_n)$ 为格 $\mathit{\Omega}$ 的一组 LLL 约化基。若

$$
c>2^{(n-1)/2+(n-d)(n-d-1)/4}\det(\overline{\mathit{\Lambda}})
$$
则 $(p_{\downarrow}(\mathbf{x}_1),p_{\downarrow}(\mathbf{x}_2),…,p_{\downarrow}(\mathbf{x}_{n-d}))$ 为 $\overline{\mathit{\Lambda}}$ 的一组 LLL 约化基。

使用阿达马不等式，我们得到以下算法：

算法5 给定一组 $\mathbf{Z}^n$ 上格 $\mathit{\Lambda}$ 的基 $(\mathbf{b}_1,\mathbf{b}_2,…,\mathbf{b}_d)$ ，该算法计算一组 $\overline{\mathit{\Lambda}}$ 的LLL约化基。

  1. 选取 $c=\lceil2^{(n-1)/2+(n-d)(n-d-1)/4}\prod^d_{j=1}||\mathbf{b}_j||\rceil$

  2. 计算 $(n+d)\times n$ 的整数矩阵 $B^-$ 和 $\mathbf{b}_1,…,\mathbf{b}_d$ 对应的 $n\times d$ 矩阵 $B=(b_{i,j})$

  3. 计算由 $B^-$ 张成的格的一组 LLL 约化基 $(\mathbf{x}_1,\mathbf{x}_2,…,\mathbf{x}_n)$

  4. 输出 $(p_{\downarrow}(\mathbf{x}_1),p_{\downarrow}(\mathbf{x}_2),…,p_{\downarrow}(\mathbf{x}_{n-d}))$

可以证明，这是一个关于空间维数 $n$ 、格维数 $d$ 和 $||\mathbf{b}_j||$ 比特长度的任何上界的确定性多项式时间算法。在实践中，不需要选择这样大的常数 $c$ ，因为 LLL 算法的理论界非常悲观。（翻译了这么久都看不懂，我也很悲观.jpg）

笔者注记：
$\lceil$和$\rceil$表示向上取整，例如$\lceil 1.2 \rceil = 2$。

实现

之前看过 Herry 师傅从 dbt 那抄的一个求法是用左零空间求解，代码如下

1
2
3
def orthogonal_lattice(B):
    LB = B.transpose().left_kernel(basis="LLL").basis_matrix()
    return LB

但笔者发现这样似乎只能在低维下求解，高维情况下时间会爆炸（至少试过一夜都没跑出来）
于是照着 paper 搓了一个 implemention ，快了很多，三分钟左右就能求解 $255\times512$ 矩阵的正交格，代码如下

1
2
3
4
5
6
7
8
9
10
def orthogonal_lattice(B):
    _d, _n = B.nrows(), B.ncols()
    _c = 2 ** min(((_n-1)/2+(_n-_d)*(_n-_d-1)/4),20)    # this bound can be adjusted as needed
    for b in B:
        _c *= b.norm()
    B_bot = (ceil(_c)*B).stack(identity_matrix(ZZ, _n))
    B_r = B_bot.transpose().LLL()
    LB = B_r.matrix_from_rows_and_columns(range(_n-_d), range(_d,_n+_d))
    assert (B*LB.transpose()).is_zero()
    return LB

参考

2022巅峰极客 Crypto

https://blog.weyung.cc/2022/08/18/2022巅峰极客 Crypto/

作者

未央

发布于

2022-08-18

更新于

2024-06-02

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

目录

最新文章

分类

标签

C2
CTF10
CVP1
Code-server1
Linux2
Nginx1
PHP1
Python3
SSL1
VSCode2
WSL1
Web2
Windows2
pwn1
二进制安全1
代理1
前端2
复变函数1
学习1
密码学9
抽象代数7
数学10
杂谈2
材料力学1
格2
汇编1
渗透1
生活1
电影1
算法2
计算机1
计算机网络2
论文3
高数3

归档

×